The present invention relates to systems and methods for encoding and/or decoding data, and more particularly to systems and methods for encoding and/or decoding using multi-stage fountain codes, herein referred to collectively as “MS Codes.”
Fountain codes have been described previously such as in Luby I, Shokrollahi I and Luby05. As described therein, sometimes referred to “chain reaction codes” in view of some of the decoding techniques, fountain codes provide a form of forward error-correction that enables data reconstruction from a received data set of a given size, without regard to the particular data packets received and provide for sequences of encoded that does not need to repeat over normal use, such that a set of data can be encoded with a fountain code to generate as much output sequence data as needed. Unlike many coding techniques that generate a fixed amount of output for a given input and thus have a predetermined “code rate”, fountain codes can be “rateless” codes. Fountain codes are often considered information additive codes in that randomly selected output symbols are likely to contribute (add) information to other randomly selected output symbols, whereas random selections of among fixed rate code symbols are more likely to be duplicative of selections already received.
As a result, communication systems employing fountain codes are able to communicate information much more efficiently compared to traditional FEC codes transmitted via data carousel or acknowledgement-based protocols, as described in Luby I, or Shokrollahi I or Luby05.
Transmission of data between a sender and a recipient over a communications channel has been the subject of much literature. Preferably, but not exclusively, a recipient desires to receive an exact copy of data transmitted over a channel by a sender with some level of certainty. Where the channel does not have perfect fidelity (which covers most of all physically realizable systems), one concern is how to deal with data lost or garbled in transmission. Lost data (erasures) are often easier to deal with than corrupted data (errors) because the recipient cannot always tell when corrupted data is data received in error. Many error-correcting codes have been developed to correct for erasures and/or for errors. Typically, the particular code used is chosen based on some information about the infidelities of the channel through which the data is being transmitted and the nature of the data being transmitted. For example, where the channel is known to have long periods of infidelity, a burst error code might be best suited for that application. Where only short, infrequent errors are expected, a simple parity code might be best.
Data transmission between multiple senders and/or multiple receivers over a communications channel has also been the subject of much literature. Typically, data transmission from multiple senders requires coordination among the multiple senders to allow the senders to minimize duplication of efforts. In a typical multiple sender system sending data to a receiver, if the senders do not coordinate which data they will transmit and when, but instead just send segments of the file, it is likely that a receiver will receive many useless duplicate segments. Similarly, where different receivers join a transmission from a sender at different points in time, a concern is how to ensure that all data the receivers receive from the sender is useful. For example, suppose the sender is wishes to transmit a file, and is continuously transmitting data about the same file. If the sender just sends segments of the original file and some segments are lost, it is likely that a receiver will receive many useless duplicate segments before receiving one copy of each segment in the file. Similarly, if a segment is received in error multiple times, then the amount of information conveyed to the receiver is much less than the cumulative information of the received garbled data. Often this leads to undesirable inefficiencies of the transmission system, or may require transmitter and/or receiver coordination.
Often data to be transmitted over a communications channel is partitioned into equal size input symbols. The “size” of an input symbol can be measured in bits, whether or not the input symbol is actually broken into a bit stream, where an input symbol has a size of M bits when the input symbol is selected from an alphabet of 2M symbols.
A coding system may produce output symbols from the input symbols. Output symbols are elements from an output symbol alphabet. The output symbol alphabet may or may not have the same characteristics as the alphabet for the input symbols. Once the output symbols are created, they are transmitted to the receivers.
The task of transmission may include post-processing of the output symbols so as to produce symbols suitable for the particular type of transmission. For example, where transmission constitutes sending the data from a wireless provider to a wireless receiver, several output symbols may be lumped together to form a frame, and each frame may be converted into a wave signal in which the amplitude or the phase is related to the frame. The operation of converting a frame into a wave is often called modulation, and the modulation is further referred to as phase or amplitude modulation depending on whether the information of the wave signal is stored in its phase or in its amplitude. Nowadays this type of modulated transmission is used in many applications, such as satellite transmission, cable modems, Digital Subscriber Lines (DSL), and many others.
A transmission is called reliable if it allows the intended recipient to recover an exact copy of the original data even in the face of errors and/or erasures during the transmission. Recovery of erased information has been the subject of much literature and very efficient coding methods have been devised in this case. Fountain codes, as described in Luby I or Shokrollahi I or Luby05, are efficient coding methods for recovery of erasures in a wide variety of settings.
One solution that has been proposed to increase reliability of transmission is to use Forward Error-Correction (FEC) codes, such as Reed-Solomon codes, Tornado codes, or, more generally, LDPC (“low density parity codes”). With such codes, one sends output symbols generated from the content instead of just sending the input symbols that constitute the content. Traditional error correcting codes, such as Reed-Solomon or other LDPC codes, generate a fixed number of output symbols for a fixed length content. For example, for K input symbols, N output symbols might be generated. These N output symbols may comprise the K original input symbols and N-K redundant symbols. If storage permits, then the sender can compute the set of output symbols for each piece of data only once and transmit the output symbols using a carousel protocol.
One problem with some FEC codes is that they require excessive computing power or memory to operate. Another problem is that the number of output symbols must be determined in advance of the coding process. This can lead to inefficiencies if the error rate of the symbols is overestimated, and can lead to failure if the error rate is underestimated. Moreover, traditional FEC schemes often require a mechanism to estimate the reliability of the communications channel on which they operate. For example, in wireless transmission the sender and the receiver are in need of probing the communications channel so as to obtain an estimate of the noise and hence of the reliability of the channel. In such a case, this probing has to be repeated quite often, since the actual noise is a moving target due to rapid and transient changes in the quality of the communications channel.
For traditional FEC codes, the number of valid output symbols that can be generated is of the same order of magnitude as the number of input symbols the content is partitioned into and is often a fixed ratio called the “code rate.” Typically, but not exclusively, most or all of these output symbols are generated in a preprocessing step before the sending step. These output symbols often have the property that all the input symbols can be regenerated from any subset of the output symbols equal in length to the original content or slightly longer in length than the original content. Typically, a code rate is selected to match an expected error rate.
Fountain decoding is a form of forward error-correction that addresses the above issues in cases where a transmission error constitutes an erasure. For fountain codes, the pool of possible output symbols that can be generated is orders of magnitude larger than the number of the input symbols typically limited only by a resolution of a counter on the encoder rather than by a code rate, and a random output symbol from the pool of possibilities can be generated very quickly. For fountain codes, the output symbols can be generated on the fly on an as needed basis concurrent with the sending step. Fountain codes have a property that all input symbols of the content can be regenerated from any subset of a set of randomly generated and/or selected output symbols slightly longer in length than the original content.
Other descriptions of various fountain coding systems can be found in documents such as U.S. Pat. No. 6,486,803, entitled “On Demand Encoding with a Window” and U.S. Pat. No. 6,411,223 entitled “Generating High Weight Output Symbols using a Basis,” assigned to the assignee of the present application.
Some embodiments of a fountain coding system comprise an encoder and a decoder. Data may be presented to the encoder in the form of a block, or a stream, and the encoder may generate output symbols from the block or the stream on the fly. In some embodiments, for example those described in Shokrollahi I and Luby05, data may be pre-encoded off-line, or concurrently with the process of transmission, using a static encoder, and the output symbols may be generated from the static input symbols, defined as the plurality of the original data symbols, and the output symbols of the static encoder.
In general, the block or stream of symbols from which the dynamic output symbols are generated is referred to herein as “source symbols.” Thus, in the case of the codes described in Shokrollahi I and Luby05, the source symbols are the static input symbols, while for codes described in Luby I, the source symbols are the input symbols. The term “input symbols” herein refers to the original symbols presented to the encoder for encoding. Thus, for chain reaction codes described in Luby I, the source symbols are identical with input symbols. Sometimes, to distinguish between an MS code, as for example one of the codes described in Shokrollahi I or Luby05, and the codes described in Luby I, we will refer herein to the output symbols generated by a coding system employing an MS code as the “dynamic output symbols.”
In certain applications, it may be preferable to transmit the input symbols first, and then continue transmission by sending generated output symbols. Such a coding system is called a systematic coding system and systematic coding systems for codes such as those described in Luby I and Shokrollahi I are disclosed in U.S. Pat. No. 6,909,383 entitled, “Systematic Encoding and Decoding of Chain Reaction Codes,” assigned to the assignee of the present application (hereinafter “Systematic MS”), whereas Luby05 is itself a systematic MS code that is designed using the elements described in “Systematic MS”.
Various methods for generating source symbols from the input symbols are described in Shokrollahi I and Luby05. Generally, but not exclusively, the source symbols are preferably generated efficiently on a data processing device, and, at the same time, a good erasure correcting capability is required of the multi-stage code. One of the teachings in Shokrollahi I and Luby05 is to use a combination of codes to produce the source symbols. In one particular embodiment described in Luby05, this combination comprises using an LDPC code to produce a second set of source symbols from the input symbols (the input symbols are the first set of source symbols) and then using a Half-Weight encoder to produce a third set of source symbols from the first two sets of source symbols, and then the dynamic output symbols are calculated based on all three sets of source symbols.
Other methods and processes for both the generation of source symbols and dynamic output symbols, and the decoding of these output symbols, have been described in U.S. Pat. No. 6,856,263 entitled “Systems and Processes for Decoding a Chain Reaction Code Through Inactivation,” assigned to the assignee of the present application (hereinafter “Inactivation Decoding”). One advantage of a decoder according teachings Inactivation Decoding over a multi-stage chain reaction decoder described in Shokrollahi I is that an inactivation decoding decoder has typically a lower probability of error.
The encoding for an MS encoder in some embodiments can be partitioned into two stages. The first stage computes redundant symbols from the original input symbols, and the second stage generates output symbols from combinations of the original input symbols and redundant symbols. In some embodiments of an MS encoder, the first stage can be further partitioned into two or more steps, where some of these steps compute redundant symbols based on Low Density Parity Check (LDPC) codes or other codes, and where other steps compute redundant symbols based on other codes. To lower the probability of error of the decoder, both multi-stage fountain decoding and some embodiments of decoding described in Inactivation Decoding may make use of a Half-Weight code in these other steps, and thus a Half-Weight code is used in these embodiments in one of the primary stages of static encoding.
The techniques of multi-stage encoding, multi-stage fountain decoding and Inactivation Decoding may also be applied to other forward error correction codes including LDPC (“low density parity check”) codes, IRA (“Irregular Repeat Accumulate”) code, AIRA (“Accumulate Irregular Repeat Accumulate”) codes, and LDGM (“low density generator matrix”) codes, and many other classes of codes based on graphs, and thus the techniques described herein for Half-Weight code generation may also be applied in those settings.
As described in Luby05, a Half-Weight code generates, for a given number k of first source symbols, a number h of redundant symbols (referred to as the “Half-Weight symbols” hereinafter). The number h is the smallest integer with the property illustrated in Equation 1, where for positive integers i and j with i>j, the function choose(i, j) is equal to i!/((i−j)!·j!) and n!=1·2· . . . ·(n−1)·n, and where for real-valued x the function ceil(x) is the smallest integer greater than or equal to x.choose(h, ceil(h/2))≧k  (Equ. 1)
As described in Luby05, Half-Weight symbols can be calculated in a specific way from the k source symbols. Using the straightforward method for the computation of these symbols, each Half-Weight symbol requires, on average, around k/2 XORs of source symbols, and thus, in total, the h Half-Weight symbols require around (k/2)·h XORs of source symbols. Since h is of the order log(k), this amounts to roughly k·log(k)/2 XORs of input symbols for the calculation of the Half-Weight symbols. Taking into account that other redundant symbols calculated via, for example LDPC encoding, require much less computational time, the calculation of the Half-Weight symbols using the straightforward approach would constitute a computational bottleneck for the design of some embodiments of reliable multi-stage encoders.
What is therefore needed is an apparatus or process for calculating the Half-Weight symbols that is much more efficient than the straightforward one, and can be implemented easily on various computing devices.